其他
看完这篇 HashMap ，和面试官扯皮就没问题了
The following article is from Java建设者 Author cxuan
桶(bucket)。遍历 HashMap 需要的时间损耗为 HashMap 实例桶的数量 + (key - value 映射) 的数量。因此，如果遍历元素很重要的话，不要把初始容量设置的太高或者负载因子设置的太低。Collections.synchronizedMap(new HashMap) 来创建一个线程安全的 Map。ConcurrentModificationException 异常。相同点
key-value 键值对，HashMap 和 HashTable 都实现了 Map、Cloneable、Serializable 接口。不同点
父类不同：HashMap 继承了
AbstractMap类，而 HashTable 继承了Dictionary类
空值不同：HashMap 允许空的 key 和 value 值，HashTable 不允许空的 key 和 value 值。HashMap 会把 Null key 当做普通的 key 对待。不允许 null key 重复。
线程安全性：HashMap 不是线程安全的，如果多个外部操作同时修改 HashMap 的数据结构比如 add 或者是 delete，必须进行同步操作，仅仅对 key 或者 value 的修改不是改变数据结构的操作。可以选择构造线程安全的 Map 比如 Collections.synchronizedMap或者是ConcurrentHashMap。而 HashTable 本身就是线程安全的容器。性能方面：虽然 HashMap 和 HashTable 都是基于单链表的，但是 HashMap 进行 put 或者 get 操作，可以达到常数时间的性能；而 HashTable 的 put 和 get 操作都是加了 synchronized锁的，所以效率很差。
初始容量不同：HashTable 的初始长度是11，之后每次扩充容量变为之前的 2n+1（n为上一次的长度）
而 HashMap 的初始长度为16，之后每次扩充变为原来的两倍。创建时，如果给定了容量初始值，那么HashTable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。
HashMap,AbstractMap和 Map 了，HashMap 我们上面已经在概述中简单介绍了一下，下面来介绍一下 AbstractMap。AbstractMap 类
Map 接口
重要内部类和接口
Node 接口
Map.Entry接口，我们先来看一下 Map中的内部接口 Entry 接口的定义// 这个唯一的方式是从集合的视图进行迭代，获取一个map的entry链。这些Map.Entry链只在
// 迭代期间有效。
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
final int hash;
// 键
final K key;
// 值
V value;
// 指向下一个Node节点的Node类型
Node<K,V> next;
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
KeySet 内部类
keyset() 方法来创建 KeySet 实例的，旨在对HashMap 中的key键进行操作，看一个代码示例public Set<K> keySet() {
// // keySet 指向的是 AbstractMap 中的 keyset
Set<K> ks = keySet;
if (ks == null) {
// 如果 ks 为空，就创建一个 KeySet 对象
// 并对 ks 赋值。
ks = new KeySet();
keySet = ks;
}
return ks;
}
Values 内部类
key-value 键值对中的 value 值进行使用，看一下代码示例：// values 其实是 AbstractMap 中的 values
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
EntrySet 内部类
key-value 键值对进行操作的内部类，它就是 EntrySet，来看一下EntrySet 的创建过程：public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
HashMap 1.7 的底层结构
final K key;
V value;
Entry<K,V> next;
int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
...
}
HashMap 1.8 的底层结构
resize() 方法。HashMap 重要属性
「初始容量」
DEFAULT_INITIAL_CAPACITY 属性管理的。左移操作，它相当于是位 是代表着符号为，0 -> 正数，1 -> 负数，容量不可能是负数，所以 HashMap 最高位只能移位到 2 ^ 30 次幂。.f 为单位，负载因子是和扩容机制有关，这里大致提一下，后面会细说。扩容机制的原则是当 HashMap 中存储的数量 > HashMap 容量 * 负载因子时，就会把 HashMap 的容量扩大为原来的二倍。resize，resize 后数组的长度扩容为原来的二倍。size 来表示 HashMap 中键值对的数量。modCount 来表示修改次数，主要用于做并发修改 HashMap 时的快速失败 - fail-fast 机制。threshold 表示扩容的阈值，也就是 初始容量 * 负载因子的值。tableSizeFor 源码解决的。我们先看一下它的源码再来解释int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
|= ，它表示的是按位或，啥意思呢？你一定知道 「a+=b 的意思是 a=a+b」，那么同理：a |= b 就是 a = a | b，也就是双方都转换为二进制，来进行与操作。如下图所示loadFactor 表示负载因子，它表示的是 HashMap 中的密集程度。HashMap 构造函数
带有 初始容量 initialCapacity和负载因子 loadFactor的构造函数
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 扩容的阈值
this.threshold = tableSizeFor(initialCapacity);
}
IllegalArgumentException 异常。如果传递进来的初始容量 > 最大容量时，初始容量 = 最大容量。负载因子也不能小于 0 。然后进行数组的扩容，这个扩容机制也非常重要，我们后面进行探讨只带有 initialCapacity 的构造函数
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
0.75f无参数的构造函数
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
带有 map 的构造函数
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
讲一讲 HashMap put 的全过程
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果table 为null 或者没有为 table 分配内存，就resize一次
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 指定hash值节点为空则直接插入，这个(n - 1) & hash才是表中真正的哈希
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果不为空
else {
Node<K,V> e; K k;
// 计算表中的这个真正的哈希值与要插入的key.hash相比
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 若不同的话，并且当前节点已经在 TreeNode 上了
else if (p instanceof TreeNode)
// 采用红黑树存储方式
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// key.hash 不同并且也不再 TreeNode 上，在链表上找到 p.next==null
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 在表尾插入
p.next = newNode(hash, key, value, null);
// 新增节点后如果节点个数到达阈值，则进入 treeifyBin() 进行再次判断
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果找到了同 hash、key 的节点，那么直接退出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 更新 p 指向下一节点
p = e;
}
}
// map中含有旧值，返回旧值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// map调整次数 + 1
++modCount;
// 键值对的数量达到阈值，需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
putVal 方法，这个方法是 final 的，如果你自已定义 HashMap 继承的话，是不允许你自己重写 put 方法的，然后这个方法涉及五个参数hash -> put 放在桶中的位置，在 put 之前，会进行 hash 函数的计算。 key -> 参数的 key 值 value -> 参数的 value 值 onlyIfAbsent -> 是否改变已经存在的值，也就是是否进行 value 值的替换标志 evict -> 是否是刚创建 HashMap 的标志
return putVal(hash(key), key, value, false, true);
}
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Hash 函数
hashCode 值，然后再对 hashcode 进行无符号右移操作，最后再和 hashCode 进行异或 ^ 操作。>>>: 无符号右移操作，它指的是 「无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0」 ，也就是不管是正数还是负数，右移都会在空缺位补 0 。重新分配，这里还涉及到一个 resize() 扩容机制源码分析，我们后面会介绍。扩容完毕后，会计算出 HashMap 的存放位置，通过使用 「( n - 1 ) & hash」 进行计算得出。扩容机制
resize() 方法来实现的，下面我们就来一次认识下。（贴出中文注释，便于复制）Node<K,V>[] oldTab = table;
// 存储old table 的大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 存储扩容阈值
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 如果old table数据已达最大，那么threshold也被设置成最大
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 左移扩大二倍,
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 扩容成原来二倍
newThr = oldThr << 1; // double threshold
}
// 如果oldThr !> 0
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 如果old table <= 0 并且 存储的阈值 <= 0
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果扩充阈值为0
if (newThr == 0) {
// 扩容阈值为 初始容量*负载因子
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 重新给负载因子赋值
threshold = newThr;
// 获取扩容后的数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果第一次进行table 初始化不会走下面的代码
// 扩容之后需要重新把节点放在新扩容的数组中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 重新映射时，需要对红黑树进行拆分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍历链表，并将链表节点按原顺序进行分组
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 将分组后的链表映射到新桶中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
判断 HashMap 中的数组的长度，也就是 (Node<K,V>[])oldTab.length()，再判断数组的长度是否比最大的的长度也就是 2^30 次幂要大，大的话直接取最大长度，否则利用位运算<<扩容为原来的两倍
如果数组长度不大于0 ，再判断扩容阈值 threshold是否大于 0 ，也就是看有无外部指定的扩容阈值，若有则使用，这里需要说明一下 threshold 何时是oldThr > 0，因为 oldThr = threshold ，这里其实比较的就是 threshold，因为 HashMap 中的每个构造方法都会调用HashMap(initCapacity,loadFactor)这个构造方法，所以如果没有外部指定 initialCapacity，初始容量使用的就是 16，然后根据this.threshold = tableSizeFor(initialCapacity);求得 threshold 的值。
否则，直接使用默认的初始容量和扩容阈值，走 else 的逻辑是在 table 刚刚初始化的时候。
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 一直以为这是常量做乘法，怎么会为 0 ，其实不是这部分的问题，在于上面逻辑判断中的扩容操作，可能会导致位溢出。float ft = (float)newCap * loadFactor; 这个方法是 2^28 * 2^(3+n) 会直接 > 2^31 次幂，导致全部归零。循环桶中的每个 Node 节点，判断 Node[i] 是否为空，为空直接返回，不为空则遍历桶数组，并将键值对映射到新的桶数组中。
如果不为空，再判断是否是树形结构，如果是树形结构则按照树形结构进行拆分，拆分方法在
split方法中。如果不是树形结构，则遍历链表，并将链表节点按原顺序进行分组。
讲一讲 get 方法全过程
get 方法的过程，Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 找到真实的元素位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 总是会check 一下第一个元素
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果不是第一个元素，并且下一个元素不是空的
if ((e = first.next) != null) {
// 判断是否属于 TreeNode，如果是 TreeNode 实例，直接从 TreeNode.getTreeNode 取
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 如果还不是 TreeNode 实例，就直接循环数组元素，直到找到指定元素位置
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
TreeNode 实例，如果是 TreeNode 实例，则直接使用 TreeNode.getTreeNode 取出元素，否则执行循环，直到下一个元素为 null 位置。getNode 方法有一个比较重要的过程就是 「(n - 1) & hash」，这段代码是确定需要查找的桶的位置的，那么，为什么要 (n - 1) & hash 呢？public static void main(String[] args) {
Map<String,Object> map = new HashMap<>();
// debug 得知 1 的 hash 值算出来是 49
map.put("1","cxuan");
// debug 得知 1 的 hash 值算出来是 50
map.put("2","cxuan");
// debug 得知 1 的 hash 值算出来是 51
map.put("3","cxuan");
}
HashMap 的遍历方式
HashIterator，它是一个 Hash 迭代器，它是一个 HashMap 内部的抽象类，它的构造比较简单，只有三种方法，「hasNext 、 remove 和 nextNode」 方法，其中 nextNode 方法是由三种迭代器实现的KeyIterator，对 key 进行遍历ValueIterator，对 value 进行遍历EntryIterator， 对 Entry 链进行遍历
HashIterator 中的 nextNode 方法进行遍历implements Iterator<K> {
public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
Node<K,V> next; // 下一个 entry 节点
Node<K,V> current; // 当前 entry 节点
int expectedModCount; // fail-fast 的判断标识
int index; // 当前槽
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {...}
}
nextNode() 方法的遍历方式和 HashIterator 的遍历方式一样，只不过判断条件不一样，构造 HashIterator 的时候判断条件是有没有链表，桶是否为 null，而遍历 nextNode 的判断条件变为下一个 node 节点是不是 null ，并且桶是不是为 null。HashMap 中的移除方法
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
关于 HashMap 的面试题
HashMap 的数据结构
位桶 + 链表的实现，即使用链表来处理冲突，同一 hash 值的链表都存储在一个数组中。但是当位于一个桶中的元素较多，即 hash 值相等的元素较多时，通过 key 值依次查找的效率较低。HashMap 的 put 过程
HashMap 为啥线程不安全
HashMap 是如何处理哈希碰撞的
HashMap 是如何 get 元素的
TreeNode 实例，如果是 TreeNode 实例，则直接使用 TreeNode.getTreeNode 取出元素，否则执行循环，直到下一个元素为 null 位置。HashMap 和 HashTable 有什么区别
HashMap 和 HashSet 的区别
HashMap 是如何扩容的
loadFactor ，一个是 threshold ，loadFactor 表示的就是负载因子，threshold 表示的是下一次要扩容的阈值，当 threshold = loadFactor * 数组长度时，数组长度扩大位原来的两倍，来重新调整 map 的大小，并将原来的对象放入新的 bucket 数组中。HashMap 的长度为什么是 2 的幂次方
例如长度为 9 时候，3 & (9-1) = 0，2 & (9-1) = 0 ，都在 0 上，碰撞了；
HashMap 线程安全的实现有哪些
ConcurrentHashMap ，或者使用线程安全的 HashMap，使用 Collections 包下的线程安全的容器，比如说